grid=[[0,1,0],[0,0,0],[0,0,1]]
direction=[-1,0,1,0,-1]

def dfs(points,grid,m,n,i,j):
    if i<0 or j<0 or i>=m or j>=n:
        return None
    if grid[i][j]==2:
        return None
    if grid[i][j]==0:
        #将在过程中遇到的为0的值都存入一个队列中
        points.append([i,j])
        return None
    grid[i][j]=2
    #相应点左侧的点
    dfs(points,grid,m,n,i-1,j)
    #右侧的点
    dfs(points,grid,m,n,i+1,j)
    dfs(points,grid,m,n,i,j-1)
    dfs(points,grid,m,n,i,j+1)
def shortestBridge(grid):
    #m代表行，n代表列
    m,n=len(grid),len(grid[0])
    #做一个队列
    points=[]
    #dfs寻找到第一个岛屿，并把1全部赋值为2
    flipped=False
    for i in range(m):
        if flipped:
            break
        for j in range(n):
            if grid[i][j]==1:
                dfs(points,grid,m,n,i,j)
                #用于控制找到第一个岛之后的跳出操作
                flipped=True #表示找到第一个岛了
                break
    #使用bfs算法寻找第二个岛屿，并把这个过程中经过的0赋值为2
    level=0
    while len(points)>0:
        level+=1
        n_points=len(points)
        while n_points>0:
            #从队列中弹出第一个元素
            [r,c]=points.pop(0)
            for k in range(4):
                x,y=r+direction[k],c+direction[k+1]
                if x>=0 and y>=0 and x<m and y<n:
                    #坐标符合规则
                    if grid[x][y]==2:
                        continue
                    if grid[x][y]==1:
                        return level
                    points.append([x,y])
                    grid[x][y]=2
            n_points-=1
    return 0
print(shortestBridge(grid))
